package codingforgreat.class19;

import java.util.HashMap;
import java.util.LinkedHashMap;

public class Class01_LRUCache {
    public Class01_LRUCache(int capacity) {
        cache = new MyCache<>(capacity);
    }

    private MyCache<Integer, Integer> cache;

    public int get(int key) {
        Integer ans = cache.get(key);
        return ans == null ? -1 : ans;

    }

    public void put(int key, int value) {
        cache.put(key, value);
    }

    public class Node<K,V>{
       public K key;
       public V value;
       public Node<K,V> pre;
       public Node<K,V> next;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
    public class NodeDoubleLinkedList<K,V> {
        public Node<K,V> head;
        public Node<K,V> tail;

        public NodeDoubleLinkedList() {
            head = null;
            tail = null;
        }
        public void addNode(Node<K,V> newNode) {
            if(newNode == null){
                return;
            }
            if(head == null){
                head = newNode;
                tail = newNode;
            }else{
               tail.next = newNode;
               newNode.pre = tail;
               tail = newNode;
            }
        }

        // node 入参，一定保证！node在双向链表里！
        // node原始的位置，左右重新连好，然后把node分离出来
        // 挂到整个链表的尾巴上
        public void moveNodeToTail(Node<K, V> node) {
            if(node == tail){
                return;
            }
            //剥离
            if(node == head){
               head = head.next;
               head.pre = null;
               node.next = null;
            }else{
                Node<K, V> pre = node.pre;
                Node<K, V> post = node.next;
                pre.next = post;
                post.pre = pre;
                node.pre = null;
                node.next = null;
            }
            //连到队尾
            addNode(node);

        }

        public Node<K, V> removeHead() {
            if (head == null) {
                return null;
            }
            Node<K, V> res = head;
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                head = res.next;
                res.next = null;
                head.next = null;
            }
            return res;
        }

    }
    public class MyCache<K,V>{
        public int capacity;
        public HashMap<K,Node<K,V>> map;
        public NodeDoubleLinkedList<K,V> dList;
        public MyCache(int capacity){
            this.capacity = capacity;
            map = new HashMap<>();
            dList = new NodeDoubleLinkedList<>();
        }
        public V get(K key) {
            if(!map.containsKey(key)){
                return null;
            }else{
                Node<K, V> res = map.get(key);
                dList.moveNodeToTail(res);
                return res.value;
            }
        }

        public void put(K key, V value) {
            if(map.containsKey(key)){
                Node<K, V> res = map.get(key);
                res.value = value;
                dList.moveNodeToTail(res);
            }else{
                Node<K, V> newNode = new Node<K, V>(key, value);
                map.put(key, newNode);
                dList.addNode(newNode);
                if (map.size() == capacity + 1) {
                    removeMostUnusedCache();
                }
            }
        }
        public void removeMostUnusedCache() {
            Node<K, V> removeNode = dList.removeHead();
            map.remove(removeNode.key);
        }
    }
}
